package labuladong.开篇;

import com.sun.deploy.util.ArrayUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class N皇后 {
    static List<List<String>> result = new ArrayList<>();

    public static List<List<String>> solveNQueens(int n) {
        StringBuilder str = new StringBuilder();
        for(int i=0; i<n; i++) {
            str.append('.');
        }
        // 初始化
        List<String> list = new ArrayList<>();
        for(int i=0; i<n; i++) {
            list.add(str.toString());
        }
        backtrack(list, 0);
        return result;
    }

    public static void backtrack(List<String> list, int row) {
        if(row == list.size()) {
            result.add(new ArrayList<>(list));
            return;
        }
        char[] demo = list.get(row).toCharArray();
        for(int col=0; col<list.size(); col++) {
            if (!isValid(list, row, col)) {
                continue;
            }
            demo[col] = 'Q';
            list.set(row, new String(demo));
            backtrack(list, row+1);
            demo[col] = '.';
            list.set(row, new String(demo));
        }
    }

    public static boolean isValid(List<String> list, int row, int col) {
        int n = list.size();
        // 检查列是否存在Q
        for (int i=0; i<n; i++) {
            if(list.get(i).charAt(col) == 'Q')
                return false;
        }
        // 检查左上方是否存在Q
        for(int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if(list.get(i).charAt(j) == 'Q')
                return false;
        }
        // 检查右上方是否存在Q
        for(int i=row-1, j=col+1; i>=0&&j<list.size(); i--, j++) {
            if(list.get(i).charAt(j) == 'Q')
                return false;
        }
        return true;
    }

    public static  void test() {
        char[] demo = new char[] {'.', 'Q', '.', '.'};
        System.out.println(new String(demo));
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(solveNQueens(20).toArray()));
    }
}
